package exampleQuestions;

public class LCAProblem {

	static class Node {

		public Node(int i) {
			this.val = i;
		}

		Node left, right;
		int val;
	}

	/**
	 * Find Lowest common ancestor in BT
	 */
	public static void main(String[] args) {

		Node n = new Node(5);
		Node n2 = new Node(29);
		Node n3 = new Node(3);
		Node n4 = new Node(0);
		Node n5 = new Node(-3);
		Node n6 = new Node(10);
		Node n7 = new Node(17);
		Node n8 = new Node(99);
		
		n.left = n4;
		n.right = n2;
		n2.left = n5;
		n2.right = n7;
		n5.left = n3;
		n7.right = n6;
		n7.left = n8;
		
		System.out.println(getLCA(n, n8, n7).val);
	}

	private static Node getLCA(Node root, Node n1, Node n2) {

		if (root == null || n1 == null || n2 == null) {
			return null;
		} else {
			if (root == n1 || root == n2) {
				return root;
			} else {
				int left = getCount(root.left, n1, n2);
				if (left == 2) {
					return getLCA(root.left, n1, n2);
				} else if(left == 1) {
					return root;
				} else {
					return getLCA(root.right, n1, n2);
				}
			}
		}
	}

	private static int getCount(Node node, Node n1, Node n2) {

		if (node == null) {
			return 0;
		}
		int count = 0;
		if (node.val == n1.val || node.val == n2.val) {
			count++;
		}
		return count + getCount(node.left, n1, n2)
				+ getCount(node.right, n1, n2);
	}

}
